package com.liunian.algorithmstudy.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Merge56 {

	/**
	 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
	 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

	 示例 1：
	 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
	 输出：[[1,6],[8,10],[15,18]]
	 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

	 示例 2：
	 输入：intervals = [[1,4],[4,5]]
	 输出：[[1,5]]
	 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
	 */
	public int[][] merge(int[][] intervals) {
		int n = 0;
		Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
		for (int i = 1; i < intervals.length; i++) {
			if (intervals[i][0] <= intervals[i - 1][1]) {
				intervals[i][0] = intervals[i - 1][0];
				intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);
				intervals[i - 1] = null;
				n++;
			}
		}
		int[][] res = new int[intervals.length - n][2];
		int j = 0;
		for (int i = 0; i < intervals.length; i++) {
			if (intervals[i] != null) {
				res[j++] = intervals[i];
			}
		}
		return res;
	}

	public static void main(String[] args) {
		Merge56 merge = new Merge56();
		System.out.println(Arrays.deepToString(merge.merge(new int[][]{
				{1,4}, {4,6}
		})));
	}

}
